# 1.双端队列可以当成栈来使用
from collections import deque

# 2.后进先出队列可不就是栈吗
from queue import LifoQueue, Empty

class MyStack:

    def __init__(self):
        self.data_stack = LifoQueue()  # 数据栈
        self.min_stack = LifoQueue()   # 最小值栈

    def pop(self):
        if self.data_stack.empty():
            raise Empty
        self.min_stack.get()
        return self.data_stack.get()

    def push(self, new_data):
        if self.min_stack.empty():
            self.min_stack.put(new_data)
        elif self.get_min() > new_data:
            self.min_stack.put(new_data)
        else:
            self.min_stack.put(self.min_stack.get())

        self.data_stack.put(new_data)

    def get_min(self):
        if self.min_stack.empty():
            raise Empty

        min_data = self.min_stack.get()
        self.min_stack.put(min_data)

        return min_data


if __name__ == "__main__":
    s1 = MyStack()
    s1.push(3)
    print(s1.get_min())

    s1.push(4)
    print(s1.get_min())

    s1.push(1)
    print(s1.get_min())

    print(s1.pop())
    print(s1.get_min())
